<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <title>C5 User's Guide</title>
  <style>
<!--
.revvid      { color: #FFFFFF; background-color: #00AA00; font-weight: bold }
-->
  </style>
</head>
<body>
<h1><a class="mozTocH1" name="mozTocId905770"></a>C5 User's guide for
prerelease version 0.5</h1>
<h2><a class="mozTocH2" name="mozTocId507311"></a>Table of contents</h2>
<ul class="readonly" id="mozToc">
<!--mozToc h1 1 h2 2 h3 3 h4 4 h5 5 h6 6--><li><a href="#mozTocId905770">C5
User's guide for prerelease version 0.5</a>
    <ul>
      <li><a href="#mozTocId507311">Table of contents</a></li>
    </ul>
  </li>
  <li><a href="#mozTocId564527">Overview</a></li>
  <li><a href="#mozTocId86956">Interfaces</a>
    <ul>
      <li><a href="#mozTocId21725">"Proper" collection interfaces</a></li>
      <li><a href="#mozTocId721827">Dictionary interfaces</a></li>
      <li><a href="#mozTocId908053">Query result interfaces</a></li>
    </ul>
  </li>
  <li><a href="#mozTocId110895">To construct a collection</a>
    <ul>
      <li><a href="#mozTocId850165">To use an external equalityComparer</a></li>
      <li><a href="#mozTocId162938">To use an external comparer</a></li>
      <li><a href="#mozTocId957374">To make collections of collections</a></li>
    </ul>
  </li>
  <li><a href="#mozTocId486186">Special topics</a>
    <ul>
      <li><a href="#mozTocId48263">To choose a set or bag collection</a></li>
      <li><a href="#mozTocId929755">To work on part of a list: list
views</a></li>
      <li><a href="#mozTocId650306">To work with persistent red-black
trees</a></li>
      <li><a href="#mozTocId553609">To implement new collection classes
or subclass an existing one</a></li>
      <li><a href="#mozTocId753674">To present a read only view of a
collection</a></li>
    </ul>
  </li>
  <li><a href="#mozTocId6619">Collection classes by data structure/class</a></li>
  <li><a href="#mozTocId393559">Planned architecture or interface
changes for first release</a></li>
  <li><a href="#mozTocId336849">Performance details for proper
collection classes</a></li>
  <li><a href="#mozTocId712409">Performance details for dictionary
classes</a></li>
</ul>
<h1><a class="mozTocH1" name="mozTocId564527"></a>Overview<br>
</h1>
<p>C5 is a comprehensive library of collection classes for the <a
 href="http://www.ecma-international.org/publications/standards/Ecma-335.htm">Common
Language Infrastructure</a> (CLI). This guide describes prerelease
version 0.5 of&nbsp; C5. <br>
</p>
<p>C5 is a
refactoring and extension of the <a
 href="http://www.dina.kvl.dk/%7Esestoft/gcsharp/index.html#collection">generic
collection classes</a> developed by Peter Sestoft while visiting
Microsoft
Research in Cambridge.</p>
<p> Unless stated otherwise types mentioned below will belong to the
"C5"
namespace; and all code examples assume a "using C5;" clause (and no
"using System.Collection.Generics;" clause)..&nbsp;</p>
<p>The goals in the development of the library has been</p>
<ul>
  <li>
    <p class="MsoNormal"><span style="" lang="EN-US">To create a
library of collection classes for the CLI that can assist expert and
non-expert programmers on the platform to develop correct and efficient
applications.</span> </p>
  </li>
  <li>
    <p class="MsoNormal"><span style="" lang="EN-US">The library should
at least fill the gaps in the standard &#8220;System.Collections.Generics&#8221;
namespace compared to standard collection class libraries for related
object oriented languages like Java, and utilize the new facilities for
generic </span><span style="" lang="EN-US">programming. Microsoft
recently (mid 2004) seems to have changed their minds and ntend to
bridge that gap in the beta2 version of VS 2005 due at the end of 2004.</span>
    </p>
  </li>
</ul>
<p>In order to fulfill the efficiency goal, the library utilizes
first-class <a href="#datastructures">data structures</a>
inside its collection classes. The library has been constructed with
the modern
object oriented programming principle of&nbsp; "<a href="#Interfaces">code
to interfaces, not to implementations</a>" in mind, while the interface
architecture has been carefully crafted to reflect the efficient data
structures
actually existence.</p>
<p>A collection in the sense of this library is a plain "collection of
items of a single type". A collection does not impose any other logical
structure on its items than perhaps uniqueness or sequence ordering.</p>
<p>The main division line among the collection classes of this library
is the
distinction between <a href="#Proper%20collection%20interfaces">"proper"
collections</a> and <a href="#Dictionary%20interfaces">dictionaries</a>.
A
dictionary is a class that defines a partial function (or map) from one
item
type (the keys) to another one (the values). A dictionary can be viewed
as a
collection of (key,value) pairs having the property of defining a
partial
function.</p>
<p>The item type for the collection classes are always given by generic
parameters. For a proper collection, there will be a single parameter,
customarily called T, as in HashSet&lt;T&gt;. For a dictionary there
will be two - the key and value types -
as in HashDictionary&lt;K,V&gt;.</p>
<p>A collection class, or rather the data structure inside, can be
either
equality based or comparison based. An equality based collection will
have an
associated so-called equalityComparer of type <a href="main.htm#T:C5.IEqualityComparer%601">IEqualityComparer&lt;T&gt;</a>,
where T is the item type of the collection. A comparison based
collection has an
associated comparer of type <a href="main.htm#T:C5.IComparer%601">IComparer&lt;T&gt;</a>.
The section below on <a href="#Constructing">creation</a> of
collection classes
explains how the equalityComparers and comparers are chosen. NB: this design will
be modified soon, cf. <a href="#planned">Planned changes</a>.<br>
</p>
<p>Collection classes in the library have either set or bag semantics.
A set
collection can at most contain one copy of an item, while bag
collections may
contain several. One can programmatically see at runtime if an editable
collection class has set or bag semantics by checking the <a
 href="main.htm#P:C5.IExtensible%601.AllowsDuplicates">
AllowsDuplicates</a>
property. At compile time, refer to the <a href="#set%20or%20bag">set
or bag table</a>
below for an overview. <br>
</p>
<h1><a class="mozTocH1" name="mozTocId86956"></a><a name="Interfaces">Interfaces</a></h1>
<p>The C5 library is designed to make it easy to program to interfaces
instead
of implementations. In particular, all public properties and methods of
the
collection classes belong to their implemented interfaces (except for
the odd
special diagnostic method and the odd mistake to be weeded out before
release). The typical programming style
would be</p>
<blockquote>
  <p><code>IList&lt;int&gt; lst = new LinkedList&lt;int&gt;();<br>
lst.Add(7);</code></p>
</blockquote>
<p>instead of&nbsp;</p>
<blockquote>
  <p><code> LinkedList&lt;int&gt; lst = new LinkedList&lt;int&gt;();<br>
lst.Add(7);</code></p>
</blockquote>
<p>Note that with this programming style, the Add call will be compiled
to an
interface call instead of a (virtual) method call, but interface calls
on the
CLR (at least the Microsoft implementation) are at most very slightly
slower
than virtual calls, so one should not shun the interface style for
performance
reasons.</p>
<p>We will discuss the collection classes available in C5 structured
according
to the main functional interfaces of the <a
 href="#Proper%20collection%20interfaces">proper
collections</a>, the <a href="#Dictionary%20interfaces">dictionaries</a>
and the
interfaces of <a href="#Query%20result%20interfaces">query results</a>.</p>
<h2><a class="mozTocH2" name="mozTocId21725"></a><a
 name="Proper collection interfaces">"Proper" collection interfaces</a></h2>
<p>The following diagam shows the type hierarchy of the proper
collection classes:</p>
<p><img alt="Interface hierarchy" src="ClsdiagWork.png"
 style="width: 757px; height: 498px;"><br>
The&nbsp;most important interfaces - those that are directly
implemented by
collection classes - are listed to the left in this table with a short
description in the middle and all implementing classes to the
right.&nbsp;</p>
<p>Please see also the <a href="#PerformanceProper">complete
complexity table</a>
for more comprehensive guidance.</p>
<p>To identify which classes are equalityComparer or comparer based and which
classes
implement set or bag we use the following symbols:</p>
<table border="1" width="471">
  <tbody>
    <tr>
      <td width="116">set: <code class="revvid">S</code> </td>
      <td width="117"> bag: <code class="revvid">B</code> </td>
      <td width="117"> equalityComparer: <code class="revvid">H</code> </td>
      <td width="117"> comparer: <code class="revvid">C</code> </td>
    </tr>
  </tbody>
</table>
<table border="1" width="100%">
  <tbody>
    <tr>
      <th width="19%">Interface</th>
      <th width="52%">Short description</th>
      <th width="29%">Implementing classes</th>
    </tr>
    <tr>
      <td valign="top" width="19%"><a
 href="main.htm#T:C5.ICollection%601">ICollection&lt;T&gt;</a>&nbsp;</td>
      <td valign="top" width="52%">This is the fundamental&nbsp;type
of&nbsp; updateable collections. It has operations for searching for
items, for adding, updating and removing one or a bunch of items, for
clearing the collection and transforming the collection to an
array.&nbsp;
      <p>If one only needs these operations, the hash set and hash bag
classes are fastest for if we have a equalityComparer for the items and the
red-black tree classes are fastest if we must use a comparer.</p>
      </td>
      <td valign="top" width="29%"><code class="revvid">SH</code> <a
 href="main.htm#T:C5.HashSet%601">HashSet&lt;T&gt;</a><br>
      <code class="revvid">BH</code> <a
 href="main.htm#T:C5.HashBag%601">HashBag&lt;T&gt;</a><br>
      <code class="revvid">BH</code> <a
 href="main.htm#T:C5.LinkedList%601">LinkedList&lt;T&gt;</a><br>
      <code class="revvid">SH</code> <a
 href="main.htm#T:C5.HashedLinkedList%601">HashedLinkedList&lt;T&gt;</a><br>
      <code class="revvid">BH</code> <a
 href="main.htm#T:C5.ArrayList%601">ArrayList&lt;T&gt;</a><br>
      <code class="revvid">SH</code> <a
 href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt;<br>
      </a> <code class="revvid">SC</code> <a
 href="main.htm#T:C5.SortedArray%601"> SortedArray&lt;T&gt;</a><br>
      <code class="revvid">SC</code> <a
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
      <code class="revvid">BC</code> <a
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
    </tr>
    <tr>
      <td valign="top" width="19%"><a
 href="main.htm#T:C5.IPriorityQueue%601">IPriorityQueue&lt;T&gt;</a>&nbsp;</td>
      <td valign="top" width="52%">This is a special case in the
library, being the only type of updateable collection interface that
does not implement IEditableCollection&lt;T&gt;. The reason for its
presence is the specialized "heap" data structures for priority queues
that only support these operations.
      <p>If one only needs these the priority queue operations and is
satisfied with bag semantics, then IntervalHeap&lt;P&gt;&nbsp; is the
fastest choice. </p>
      </td>
      <td valign="top" width="29%"> <code class="revvid">BC</code> <a
 href="main.htm#T:C5.IntervalHeap%601">IntervalHeap&lt;T&gt;</a><br>
      <code class="revvid">SC</code> <a
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
      <code class="revvid">BC</code> <a
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
    </tr>
    <tr>
      <td valign="top" width="19%"><a href="main.htm#T:C5.IList%601">IList&lt;T&gt;</a>&nbsp;</td>
      <td valign="top" width="52%">This is an updateable collection
with sequence order imposed on the items by the user at insertion time
or by later rearrangements.&nbsp;
      <p>There are two main base data structures: dynamic arrays and
doubly linked lists with very different complexity profile.&nbsp;The
plain linked list is fast for operations at the end points only, while
the plain array list have very fast lookups by index, but update
operations are only fast at the right end point.&nbsp;</p>
      <p>The Hashed- variants employ an index based on a hash table.
This speeds up lookups by item considerably and for the linked list
variant also insertions before or after specific items. The index
changes the classes from bags to sets.&nbsp;</p>
      <p>The hashed variants more than double the time of otherwise
fast update operations, and should only be used when really
needed.&nbsp;</p>
      </td>
      <td valign="top" width="29%"> <code class="revvid">BH</code> <a
 href="main.htm#T:C5.LinkedList%601"> LinkedList&lt;T&gt;</a><br>
      <code class="revvid">SH</code> <a
 href="main.htm#T:C5.HashedLinkedList%601"> HashedLinkedList&lt;T&gt;</a><br>
      <code class="revvid">BH</code> <a
 href="main.htm#T:C5.ArrayList%601"> ArrayList&lt;T&gt;</a><br>
      <code class="revvid">SH</code> <a
 href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt;</a></td>
    </tr>
    <tr>
      <td valign="top" width="19%"><a
 href="main.htm#T:C5.IIndexedSorted%601">IIndexedSorted&lt;T&gt;</a>&nbsp;</td>
      <td valign="top" width="52%">This is an updateable collection
with sequence order given by a comparer.&nbsp;
      <p>There are two main data structures inside the implementations:
red-black search trees and a dynamic array kept sorted at all times.</p>
      <p>The differences are chiefly that the trees have much faster
update operations, while the sorted array is somewhat faster at index
lookups. In fact, the sorted array should only be used for static
operation, where the collection is created and populated and then not
changed again. </p>
      </td>
      <td valign="top" width="29%"> <code class="revvid">SC</code> <a
 href="main.htm#T:C5.SortedArray%601"> SortedArray&lt;T&gt;</a><br>
      <code class="revvid">SC</code> <a
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
      <code class="revvid">BC</code> <a
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
    </tr>
    <tr>
      <td valign="top" width="19%"><a
 href="main.htm#T:C5.IPersistentSorted%601">IPersistentSorted&lt;T&gt;</a>&nbsp;</td>
      <td valign="top" width="52%">This is a sorted collection that
support very fast clones that themselves are sorted. The only
implementation is the tree implementation with set and bag variants. </td>
      <td valign="top" width="29%"> <code class="revvid">SC</code> <a
 href="main.htm#T:C5.TreeSet%601"> TreeSet&lt;T&gt;</a><br>
      <code class="revvid">BC</code> <a
 href="main.htm#T:C5.TreeBag%601"> TreeBag&lt;T&gt;</a></td>
    </tr>
  </tbody>
</table>
<h2><a class="mozTocH2" name="mozTocId721827"></a><a
 name="Dictionary interfaces">Dictionary interfaces</a></h2>
<p>There are two dictionary interfaces:</p>
<table border="1" width="100%">
  <tbody>
    <tr>
      <th valign="top" width="19%">Interface</th>
      <th width="56%">Short description</th>
      <th width="25%">Implementing classes</th>
    </tr>
    <tr>
      <td valign="top" width="19%"><a
 href="main.htm#T:C5.IDictionary%602">IDictionary&lt;K,V&gt;</a> </td>
      <td width="56%">This is the base dictionary interface.&nbsp;
      <p>The choice is that one should use the hash dictionary unless
one only has a comparer for the items, in which case the tree
dictionary can be used.&nbsp; </p>
      </td>
      <td width="25%"><a href="main.htm#T:C5.HashDictionary%602">HashDictionary&lt;K,V&gt;</a><br>
      <a href="main.htm#T:C5.TreeDictionary%602">TreeDictionary&lt;K,V&gt;</a></td>
    </tr>
    <tr>
      <td valign="top" width="19%"><a
 href="main.htm#T:C5.ISortedDictionary%602">ISortedDictionary&lt;K,V&gt;</a>
      </td>
      <td width="56%">This is a dictionary based on a comparer for the
keys. There is only the tree implementation.&nbsp; </td>
      <td width="25%"><a href="main.htm#T:C5.TreeDictionary%602">TreeDictionary&lt;K,V&gt;</a></td>
    </tr>
  </tbody>
</table>
<h2><a class="mozTocH2" name="mozTocId908053"></a><a
 name="Query result interfaces">Query result interfaces</a></h2>
<p>Some of the most basic collection interfaces have an important usage
as the
types of results of queries to collections, although these interfaces
also
appear at the base of the other collection interfaces and even as the
types of
synthetic collections. The interfaces in question are the standard
System.Collections.Generics.IEnumerable&lt;T&gt;,
<a href="main.htm#T:C5.ICollectionValue%601">ICollectionValue&lt;T&gt;</a>,
<a href="main.htm#T:C5.IDirectedEnumerable%601">IDirectedEnumerable&lt;T&gt;</a>
and <a href="main.htm#T:C5.IDirectedCollectionValue%601">IDirectedCollectionValue&lt;T&gt;</a>.</p>
<p>The differences between the "Enumerable" and "Collection"
variants are that the "Enumerable" variant only knows how to
enumerate through its items, the "Collection" variants also knows how
many items it has (without having to walk through an enumeration). The
"Directed" variants are used for results of queries to sequenced
collections (implementing <a href="main.htm#T:C5.ISequenced%601">ISequenced&lt;T&gt;</a>)
and therefore have a non-implementation dependent enumeration order.
The
"Directed" variants supports two operations, <a
 href="main.htm#M:C5.IDirectedCollectionValue%601.Backwards">Backwards()</a>
to enable enumeration in the opposite direction and <a
 href="main.htm#P:C5.IDirectedEnumerable%601.Direction">Direction</a>
to tell if the enumeration order is forwards or backwards with respect
to the
original collection.</p>
<p>Note: operations on an enumerator created by the GetEnumerator()
method on System.Collections.Generics.IEnumerable&lt;T&gt; cannot be
interleaved with update
operations on
the underlying collection.</p>
<p>Note: for all enumerators in the library the operations have O(1)
amortized
complexity.</p>
<h1><a class="mozTocH1" name="mozTocId110895"></a>To <a
 name="Constructing">construct</a> a collection</h1>
<p>All collections classes in C5 have (zero parameter) default
constructors. So
if we want to make a linked list of items of some type, <code>TheType</code>,
and add an item to the list we will do</p>
<p><code>&nbsp;&nbsp;&nbsp; IList&lt;TheType&gt; lst = new
LinkedList&lt;TheType&gt;();<br>
&nbsp;&nbsp;&nbsp; TheType t = ...;<br>
&nbsp;&nbsp;&nbsp; lst.Add(t);</code></p>
<p>The collection classes have no constructors that will take an array
or a
collection as parameter for prepopulating the collection, use the <a
 href="file:///C:/home/kokholm/c5/vs/C5/main.htm#M:C5.ISink%601.AddAll%28C5.IEnumerable%7B%210%7D%29">
AddAll</a> method
instead. NB: in the released version, expect constructors with an
enumerable as argument and constructors with a variable number of
arguments ("params") for the initialization of the collection, see the <a
 href="#planned">planned changes</a> section.<br>
</p>
<p>Some collection classes are governed by internal parameters that one
can give
non-default values at creation time (<code>fill</code> in <a
 href="main.htm#T:C5.HashSet%601">HashSet&lt;T&gt;</a>,&nbsp;
<a href="main.htm#T:C5.HashBag%601">HashBag&lt;T&gt;</a>, <a
 href="main.htm#T:C5.HashDictionary%602">HashDictionary&lt;K,V&gt;</a>)
or use internal tables that one can expand in advance if one has
expectations of
how large the collection will grow (HashSet&lt;T&gt;,&nbsp;
HashBag&lt;T&gt;, HashDictionary&lt;K,V&gt;, <a
 href="main.htm#T:C5.ArrayList%601">ArrayList&lt;T&gt;</a>,
<a href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt;</a>,
<a href="main.htm#T:C5.SortedArray%601">SortedArray&lt;T&gt;</a>,
<a href="main.htm#T:C5.IntervalHeap%601">IntervalHeap&lt;T&gt;</a>).</p>
<p>For equality-based collection classes, these constructors will use a
default
equalityComparer to define equality of items according to the following table:</p>
<table border="1">
  <tbody>
    <tr>
      <th>T</th>
      <th>default equalityComparer (implements IEqualityComparer&lt;T&gt;)</th>
      <th>Equality and hash code by</th>
    </tr>
    <tr>
      <td>int</td>
      <td><a href="main.htm#T:C5.IntEqualityComparer">IntEqualityComparer</a></td>
      <td>Equals and hash code of integer</td>
    </tr>
    <tr>
      <td>other value type</td>
      <td><a href="main.htm#T:C5.DefaultValueTypeEqualityComparer%601">DefaultValueTypeEqualityComparer&lt;T&gt;</a></td>
      <td>methods inherited from object</td>
    </tr>
    <tr>
      <td>IEditableCollection&lt;S&gt;</td>
      <td><a href="main.htm#T:C5.EqualityComparerBuilder.UnsequencedEqualityComparer%602">EqualityComparerBuilder.UnsequencedEqualityComparer&lt;S,IEditableCollection&lt;S&gt;&gt;</a></td>
      <td>contents without regards to sequence</td>
    </tr>
    <tr>
      <td>ISequenced&lt;S&gt;</td>
      <td><a href="main.htm#T:C5.EqualityComparerBuilder.SequencedEqualityComparer%602">EqualityComparerBuilder.SequencedEqualityComparer&lt;S,IEditableCollection&lt;S&gt;&gt;</a></td>
      <td>contents with regards to sequence</td>
    </tr>
    <tr>
      <td>other reference type</td>
      <td><a href="main.htm#T:C5.DefaultReferenceTypeEqualityComparer%601">DefaultReferenceTypeEqualityComparer&lt;T&gt;</a></td>
      <td>methods inherited from object</td>
    </tr>
  </tbody>
</table>
<p>For comparison-based collection classes, these constructors will use
a
default comparer:</p>
<table border="1">
  <tbody>
    <tr>
      <th>T</th>
      <th>default comparer&nbsp;<br>
(implements IComparer&lt;T&gt;)</th>
      <th>Comparison by</th>
    </tr>
    <tr>
      <td>int</td>
      <td>IC</td>
      <td>Standard integer comparison</td>
    </tr>
    <tr>
      <td>implementing IComparable&lt;T&gt;</td>
      <td><a href="main.htm#T:C5.NaturalComparer%601">NaturalComparer&lt;T&gt;</a></td>
      <td>The CompareTo(T o)&nbsp; instance method</td>
    </tr>
    <tr>
      <td>other implementing System.IComparable</td>
      <td><a href="main.htm#T:C5.NaturalComparerO%601">NaturalComparerO&lt;T&gt;</a></td>
      <td>The CompareTo(object o) instance method</td>
    </tr>
    <tr>
      <td>other</td>
      <td>-</td>
      <td><i>collection class constructor throws an exception</i></td>
    </tr>
  </tbody>
</table>
<p>Sometimes, the default equalityComparer or comparer is not the right one for
the
problem at hand. In that case one must get hold on a equalityComparer or comparer
of the
right kind and supply it to one of the constructors of the collection
classes
that supports such a parameter. The procedure is demonstrated in the
sections
below on <a href="#external%20equalityComparer">external equalityComparers</a>, <a
 href="#external%20comparer">external
comparers</a> and <a href="#collections%20of%20collections">collections
as items</a>.<br>
</p>
<p>NB: in the released version, expect the equalityComparers and comparers to be
of the System.Collections.Generics.IComparer&lt;T&gt; type, see the <a
 href="userguide.htm#planned">planned changes</a> section.</p>
<h2><a class="mozTocH2" name="mozTocId850165"></a>To use an <a
 name="external equalityComparer"> external equalityComparer</a></h2>
<p>In addition to the helper classes referenced above, the library has
the
helper class <a href="main.htm#T:C5.KeyValuePairEqualityComparer%602">KeyValuePairEqualityComparer&lt;K,V&gt;</a>
to construct a equalityComparer for pairs of the type <a
 href="main.htm#T:C5.KeyValuePair%602">KeyValuePair&lt;K,V&gt;</a>,
the type of entry of a K to V dictionary. The constructed equalityComparer will
only take
the first component of the pair into account. We can use these classes
in the
following way to make a linked list (with hash index) of pairs of
strings
identified by their first components using some custom equalityComparer on
strings:</p>
<blockquote>
  <p><code>IEqualityComparer&lt;string&gt; csh = ...;<br>
IEqualityComparer&lt;KeyValuePair&lt;string,string&gt;&gt; cph =&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
new KeyValuePairEqualityComparer&lt;string,string&gt;(csh);<br>
IList&lt;KeyValuePair&lt;string,string&gt;&gt; lst =<br>
  </code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<code>
new HashedLinkedList&lt;KeyValuePair&lt;string,string&gt;&gt;(cph);<br>
lst.Add(new KeyValuePair&lt;string,string&gt;("abe","kat"));</code></p>
</blockquote>
<p>One may, of course, program a equalityComparer oneself. This one should always
do if
the item type is defined as a struct (value type) that does not
override the
Equals and GetHashCode methods of object, since in that case the
default equalityComparer
will use the slow default versions of those methods supplied by the
runtime via
reflection.&nbsp;</p>
<h2><a class="mozTocH2" name="mozTocId162938"></a>To use an <a
 name="external comparer"> external comparer</a></h2>
<p>There is a helper class for comparer of pairs: <a
 href="main.htm#T:C5.KeyValuePairEqualityComparer%602">KeyValuePairComparer&lt;K,V&gt;</a>.
We will show an example of a custom comparer. Imagine wanting to
compare double
precision floating point numbers with a tolerance. The following code
snippet
shows how one could make a tree set out of such numbers:</p>
<blockquote>
  <p><code>class DC : IComparer&lt;double&gt; {<br>
&nbsp;&nbsp; const double eps = 1E-10;<br>
&nbsp;&nbsp; int Compare(double a, double b)&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; {return a &gt; b + eps ? 1 : a &lt; b -
eps ? -1 : 0;}<br>
}<br>
  <br>
void dowork() {<br>
&nbsp;&nbsp; IComparer&lt;double&gt; dc = new DC();<br>
&nbsp;&nbsp; ISorted&lt;double&gt; tree = new TreeSet&lt;double&gt;(dc);<br>
&nbsp;&nbsp; tree.Add(3.45);<br>
&nbsp;&nbsp; ...<br>
}</code></p>
</blockquote>
<p>In this particular case, one would have to make sure, that two
different
floating point numbers are only identified by the comparer if they
really should
represent the same value and not by coincidence.</p>
<h2><a class="mozTocH2" name="mozTocId957374"></a>To make <a
 name="collections of collections"> collections of collections</a></h2>
<p>When one wants to use a collection whose items itself are of
collection type,
one usually wants the interior collections to be identified by contents
- either
according to or irrespective of sequence order. An example could be
transformations of <a
 href="http://www.dina.kvl.dk/%7Esestoft/gcsharp/index.html#regexp">Finite
Automatons</a>. The default equalityComparers and the EqualityComparerBuilder classes
mentioned
above may help to construct such collections of collections as in the
examples
that follow:</p>
<p>To make an array list of sequenced collections identified by
contents in
sequenced fashion one would simply do:</p>
<blockquote>
  <p><code>ArrayList&lt;ISequenced&lt;int&gt;&gt; lst = new
ArrayList&lt;ISequenced&lt;int&gt;&gt;();</code></p>
</blockquote>
<p>To make a linked list of linked lists identified by contents
unsequenced, explicitly
construct the collection equalityComparer:</p>
<blockquote>
  <p><code>IEqualityComparer&lt;LinkedList&lt;int&gt;&gt; lsth =<br>
  </code>&nbsp;&nbsp;&nbsp;&nbsp; <code>new
EqualityComparerBuilder.UnsequencedEqualityComparer&lt;int,LinkedList&lt;int&gt;&gt;();<br>
LinkedList&lt;LinkedList&lt;int&gt;&gt; lst =<br>
&nbsp;&nbsp; new LinkedList&lt;LinkedList&lt;int&gt;&gt;(lsth);</code></p>
</blockquote>
<p>If for some strange reason one would like to make a hash set of
linked lists
with the lists identified by reference equality one would simply do:</p>
<blockquote>
  <p><code>HashSet&lt;LinkedList&lt;int&gt;&gt; lst = new
HashSet&lt;LinkedList&lt;int&gt;&gt;();</code></p>
</blockquote>
<p>If for even stranger reasons one would make a hash set of
ISequenced&lt;int&gt; collections with the collections identified by
reference
equality one would do like this:</p>
<blockquote>
  <p><code>IEqualityComparer&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt;
lsth =<br>
  </code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <code>new
DefaultReferenceTypeEqualityComparer&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt;();<br>
HashSet&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt; lst =<br>
&nbsp;&nbsp; new HashSet&lt;</code><code>ISequenced</code><code>&lt;int&gt;&gt;(lsth);</code></p>
</blockquote>
<h1><a class="mozTocH1" name="mozTocId486186"></a>Special topics</h1>
<h2><a class="mozTocH2" name="mozTocId48263"></a>To choose a <a
 name="set or bag"> set or bag</a> collection</h2>
<p>The following table shows which of the collection classes have set
semantics
and which have bag semantics. All the implemented classes have fixed,
compiled in semantics. <br>
</p>
<p>Note: when in a set collection, methods with an Add in the name will
ignore
attempts to add an item already there or flag the failed attempt by a
Boolean return value; methods with an Insert in the name (only in
lists) will throw an
exception.</p>
<table border="1" width="38%">
  <tbody>
    <tr>
      <td valign="top" width="6%"><a href="main.htm#T:C5.HashSet%601">HashSet&lt;T&gt;</a></td>
      <td valign="top" width="5%">set</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a href="main.htm#T:C5.HashBag%601">HashBag&lt;T&gt;</a></td>
      <td valign="top" width="5%">bag</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a
 href="main.htm#T:C5.LinkedList%601"> LinkedList&lt;T&gt;</a></td>
      <td valign="top" width="5%">bag</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a
 href="main.htm#T:C5.HashedLinkedList%601"> HashedLinkedList&lt;T&gt;</a></td>
      <td valign="top" width="5%">set</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a
 href="main.htm#T:C5.ArrayList%601"> ArrayList&lt;T&gt;</a></td>
      <td valign="top" width="5%">bag</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a
 href="main.htm#T:C5.HashedArrayList%601"> HashedArrayList&lt;T&gt; </a>
      </td>
      <td valign="top" width="5%">set</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a
 href="main.htm#T:C5.SortedArray%601"> SortedArray&lt;T&gt;</a></td>
      <td valign="top" width="5%">set</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a href="main.htm#T:C5.TreeSet%601">TreeSet&lt;T&gt;</a></td>
      <td valign="top" width="5%">set</td>
    </tr>
    <tr>
      <td valign="top" width="6%"> <a href="main.htm#T:C5.TreeBag%601">TreeBag&lt;T&gt;</a></td>
      <td valign="top" width="5%">bag</td>
    </tr>
    <tr>
      <td valign="top" width="6%"><a
 href="main.htm#T:C5.IntervalHeap%601">IntervalHeap&lt;T&gt;</a></td>
      <td valign="top" width="5%">bag</td>
    </tr>
  </tbody>
</table>
<h2><a class="mozTocH2" name="mozTocId929755"></a>To work on part of a
list: list views</h2>
<p>The IList&lt;T&gt; interface supports via the <a
 href="main.htm#M:C5.IList%601.View%28System.Int32,System.Int32%29">
View</a>
method the functionality that one can zoom in on part of a list and use
it as an
IList&lt;T&gt; in its own right while having updates to the view passed
through
to the base (original) IList&lt;T&gt;. Using the <a
 href="main.htm#M:C5.IList%601.Slide%28System.Int32%29">Slide</a>
method calls, one may move the view around the base list. Using Slide
repeatedly
one can implement safe ways to iterate over a list while updating it.
The
IList&lt;T&gt; interface also has properties <a
 href="main.htm#P:C5.IList%601.Underlying">Underlying</a>
and <a href="main.htm#P:C5.IList%601.Offset">Offset</a> showing the
base list of a
view and the current site of a view.</p>
<p>One can create a view on a view, but the new view will have the
original base
list as base. A view will be invalidated if an update operation is
performed on
the base list by any other means than through this particular view.</p>
<p>The following code snippet shows a silly example of iterating over a
list,
doing an insertion each time certain combination of items are seen (the
example
iterates right to left and inserts 666 whenever two consecutive items
have an
odd difference):</p>
<blockquote>
  <p><code>IList&lt;int&gt; lst = ...;<br>
IList&lt;int&gt; view = lst.CreateView(lst.Count-2, 2);<br>
while (true) {<br>
&nbsp;&nbsp;&nbsp; if ((view.Last - view.First) % 2 == 1)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; view.Insert(1, 666);<br>
&nbsp;&nbsp;&nbsp; if (view.Offset == 0)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;<br>
&nbsp;&nbsp;&nbsp; else<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; view.Slide(-1,2);<br>
}</code></p>
</blockquote>
<h2><a class="mozTocH2" name="mozTocId650306"></a>To work with
persistent red-black trees</h2>
<p>The search tree implementation in the library is based on node copy
persistent red-black trees. The persistence is exposed in the <a
 href="main.htm#M:C5.IPersistentSorted%601.Snapshot">Snapshot</a>
method that can be considered a very fast and space-saving way of
making a
read-only clone of the tree. When using persistence, the space use of a
red-black tree in this implementation is linear in the number of
operations
since the creation of the tree.</p>
<p>One use of persistence could be to safely enumerate a tree
interleaved with
updates:</p>
<blockquote>
  <p><code>IPersistentSorted&lt;int&gt; tree = new TreeSet&lt;int&gt;();<br>
tree.Add(5);<br>
...<br>
ISorted&lt;int&gt; snap = tree.Snapshot();<br>
foreach (int i in snap)<br>
&nbsp;&nbsp;&nbsp; tree.Add(i+7);</code></p>
</blockquote>
<p>The GUITester project of the complete library source code contains
an
interesting (standard) usage of persistent search trees to the
geometric problem
of constructing an efficient data structure for point location in a
division of
the plane given by a list of line segments.</p>
<h2><a class="mozTocH2" name="mozTocId553609"></a>To implement new
collection classes or subclass an existing one</h2>
<p>All interface methods and properties of the collection classes
implemented in
the library are virtual and so it should be safe to subclass these
classes. Some
classes may have protected members if they are subclassed in the
library itself.
We refer to the detailed reference manuals and the library source for
information on the protected members and their role in subclassing.</p>
<p>There is a sequence of helper classes designed to be used as base
classes of
collection classes: <a href="main.htm#T:C5.EnumerableBase%601">EnumerableBase&lt;T&gt;</a>,
<a href="main.htm#T:C5.CollectionValueBase%601">CollectionValueBase&lt;T&gt;</a>,
<a href="main.htm#T:C5.CollectionBase%601">CollectionBase&lt;T&gt;</a>,
<a href="main.htm#T:C5.SequencedBase%601">SequencedBase&lt;T&gt;</a>
and <a href="main.htm#T:C5.ArrayBase%601">ArrayBase&lt;T&gt;</a>.
Please see the reference manual and the library source code for
documentation
and examples.</p>
<p>As for dictionaries, the DictionaryBase&lt;K,V&gt; class will
construct a
class implementing IDictionary&lt;K,V&gt; by simply plugging in a set
implementation.</p>
<h2><a class="mozTocH2" name="mozTocId753674"></a>To present a read
only view of a collection</h2>
<p>The library contains a long list of wrapper classes all with name
starting
with Guarded having the purpose of creating a read-only view of an
existing
collection. The wrapping is done by the constructors of the classes. If
we want
to give some code access to only lookup operations on a, say, list we
can do as
follows:</p>
<blockquote>
  <p><code>IList&lt;int&gt; lst;<br>
...<br>
IList&lt;int&gt; rolst = new GList&lt;int&gt;(lst);<br>
OtherObject.dowork(rolst);</code></p>
</blockquote>
<p>Please see the reference manual for details on available wrapper
classes.</p>
<h1><a class="mozTocH1" name="mozTocId6619"></a><a name="datastructures">Collection
classes by data structure/class</a></h1>
<p>The following table&nbsp;shows the underlying data structure of the
various collection classes.</p>
<table border="1">
  <tbody>
    <tr>
      <th>Data structure</th>
      <th>Classes</th>
      <th>Primary Interfaces</th>
    </tr>
    <tr>
      <td>hash table</td>
      <td>HashSet&lt;T&gt;</td>
      <td> ICollection&lt;T&gt;</td>
    </tr>
    <tr>
      <td>hash table</td>
      <td>HashBag&lt;T&gt;</td>
      <td> ICollection&lt;T&gt;</td>
    </tr>
    <tr>
      <td>hash table</td>
      <td>HashDictionary&lt;K,V&gt;</td>
      <td>IDictionary&lt;K,V&gt;</td>
    </tr>
    <tr>
      <td>linked list</td>
      <td>LinkedList&lt;T&gt;</td>
      <td>IList&lt;T&gt;</td>
    </tr>
    <tr>
      <td>linked list with hash index</td>
      <td>HashedLinkedList&lt;T&gt;</td>
      <td>IList&lt;T&gt;</td>
    </tr>
    <tr>
      <td>dynamic array</td>
      <td>ArrayList&lt;T&gt;</td>
      <td>IList&lt;T&gt;</td>
    </tr>
    <tr>
      <td>dynamic array with hash index</td>
      <td>HashedArrayList&lt;T&gt;</td>
      <td>IList&lt;T&gt;</td>
    </tr>
    <tr>
      <td>sorted dynamic array</td>
      <td>SortedArray&lt;T&gt;</td>
      <td>IIndexedSorted&lt;T&gt;</td>
    </tr>
    <tr>
      <td>heap</td>
      <td>IntervalHeap&lt;T&gt;</td>
      <td>IPriorityQueue&lt;T&gt;</td>
    </tr>
    <tr>
      <td>red-black search tree</td>
      <td>TreeSet&lt;T&gt;</td>
      <td>IIndexedSorted&lt;T&gt;, IPersistentSorted&lt;T&gt;</td>
    </tr>
    <tr>
      <td>red-black search tree</td>
      <td>TreeBag&lt;T&gt;</td>
      <td>IIndexedSorted&lt;T&gt;, IPersistentSorted&lt;T&gt;</td>
    </tr>
    <tr>
      <td>red-black search tree</td>
      <td>TreeDictionary&lt;K,V&gt;</td>
      <td>ISortedDictionary&lt;K,V&gt;</td>
    </tr>
  </tbody>
</table>
<br>
<h1><a class="mozTocH1" name="mozTocId393559"></a>&lt;&gt;<a
 name="planned"></a>Planned<span style="font-weight: bold;"> </span>architecture
or interface changes
for first release<br>
</h1>
<ol>
  <li>Eliminate the use of our own generic equality/comparator types,
C5.IComparer&lt;T&gt; and C5.IEqualityComparer&lt;T&gt; and use the new design of
VS 2005 beta1 in the form of the combined
System.Collections.Generic.IComparer&lt;T&gt;.</li>
  <li>Vararg (params) constructors? (And IEnum do.)</li>
  <li>Possibly extended use of "wildcard style" operations like
AddAll&lt;U&gt;(IEnumerable&lt;U&gt; items)?</li>
  <li>Make all collection classes clonable and serializable.</li>
</ol>
<h1><a class="mozTocH1" name="mozTocId336849"></a><a
 name="PerformanceProper">Performance</a> details for proper collection
classes</h1>
<p>This section overviews the complexities of cc public methods and
property
accesses.</p>
<p>In the table below, for lack of space we use the following numbers
to
identify collection classes:</p>
<table border="1">
  <tbody>
    <tr>
      <th>Class</th>
      <th>Column</th>
    </tr>
    <tr>
      <td>HashSet&lt;T&gt;</td>
      <td>HS</td>
    </tr>
    <tr>
      <td>HashBag&lt;T&gt;</td>
      <td>HB</td>
    </tr>
    <tr>
      <td>ArrayList&lt;T&gt;</td>
      <td>AL</td>
    </tr>
    <tr>
      <td>LinkedList&lt;T&gt;</td>
      <td>LL</td>
    </tr>
    <tr>
      <td>HashedArrayList&lt;T&gt;</td>
      <td>HAL</td>
    </tr>
    <tr>
      <td>HashedLinkedList&lt;T&gt;</td>
      <td>HLL</td>
    </tr>
    <tr>
      <td>TreeSet&lt;T&gt;</td>
      <td>RBTS</td>
    </tr>
    <tr>
      <td>TreeBag&lt;T&gt;</td>
      <td>RBTB</td>
    </tr>
    <tr>
      <td>SortedArray&lt;T&gt;</td>
      <td>SA</td>
    </tr>
    <tr>
      <td>IntervalHeap&lt;T&gt;</td>
      <td>IH</td>
    </tr>
  </tbody>
</table>
<p>And the following special symbols:&nbsp;</p>
<p>
n size of collection,&nbsp;<br>
m size of argument if collection-: not supported<br>
*: means: suboptimal complexity (library is in error)<br>
$: special at end: the operation is much faster at the start and/or end
(end for
array list, both for linked list)
</p>
<p>Note: we do not show return type&nbsp; or parameters for methods,
just mark
with ()<br>
Note: we ignore time for reclaiming of internal array space (e.g. Clear)<br>
User supplied operations like comparers or equalityComparers are assumed to be
O(1)</p>
<table border="1" height="2893" width="100%">
  <tbody>
    <tr>
      <th height="23" width="9%">Member</th>
      <th height="23" width="8%">HS</th>
      <th height="23" width="8%">HB</th>
      <th height="23" width="8%">AL</th>
      <th height="23" width="8%">LL</th>
      <th height="23" width="8%">HAL</th>
      <th height="23" width="8%">HLL</th>
      <th height="23" width="8%">RBTS</th>
      <th height="23" width="8%">RBTB</th>
      <th height="23" width="9%">SA</th>
      <th height="23" width="9%">IH</th>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">&nbsp;IEnumerable&lt;T&gt;</font></i></td>
      <td height="22" width="8%">&nbsp;&nbsp;</td>
      <td height="22" width="8%">&nbsp;</td>
      <td height="22" width="8%">&nbsp;</td>
      <td height="22" width="8%">&nbsp;</td>
      <td height="22" width="8%">&nbsp;</td>
      <td height="22" width="8%">&nbsp;</td>
      <td height="22" width="8%">&nbsp;</td>
      <td height="22" width="8%">&nbsp;</td>
      <td height="22" width="9%">&nbsp;</td>
      <td height="22" width="9%">&nbsp;</td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">GetEnumerator()</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">IDirectedEnumerable&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="18%"><font size="2">Direction</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="18%"><font size="2">Backwards()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">ICollectionValue&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Count</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="22" width="18%"><font size="2">CopyTo</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">ToArray</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Apply()</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Exists()</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">All()</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">IDirectedCollectionValue&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="18%"><font size="2">Backwards()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="13%"><i><font color="#808080" size="2">IExtensible&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">AllowsDuplicates</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">SyncRoot</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">IsEmpty</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Add</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">AddAll</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(mlog n)</font></td>
      <td height="22" width="8%"><font size="2">O(mlog n)</font></td>
      <td height="22" width="9%"><font size="2">O(mlog n)</font></td>
      <td height="22" width="9%"><font size="2">??</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">ICollection&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">IsReadOnly</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">ContainsSpeed</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">GetHashCode</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Equals</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Contains</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">ContainsCount</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">ContainsAll</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
      <td height="22" width="9%"><font size="2">O(m logn)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Find</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">FindOrAdd</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Update</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">UpdateOrAdd</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Remove</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveWithReturn</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveAllCopies</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveAll</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
      <td height="22" width="9%"><font size="2">O(m logn)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Clear</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RetainAll</font></td>
      <td height="22" width="8%"><font size="2">O(m)?</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
      <td height="22" width="8%"><font size="2">O(mn)*</font></td>
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
      <td height="22" width="8%"><font size="2">O(m)</font></td>
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
      <td height="22" width="8%"><font size="2">O(m logn)</font></td>
      <td height="22" width="9%"><font size="2">O(m logn)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">ISequenced&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">GetHashCode</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Equals</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">IIndexed&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">this[i]</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">this[start,end]</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">IndexOf()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">LastIndexOf()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveAt</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveInterval</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n log n)*</font></td>
      <td height="22" width="8%"><font size="2">O(n log n)*</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">IList&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HB</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">AL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">LL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HAL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">HLL</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTS</font></i></td>
      <td align="center" height="22" width="8%"><i><font color="#808080"
 size="2">RBTB</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">SA</font></i></td>
      <td align="center" height="22" width="9%"><i><font color="#808080"
 size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">First</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Last</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">FIFO</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">this[i]</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Base</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Offset</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Map()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Insert()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">InsertFirst()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">InsertLast()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">InsertBefore()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">InsertAfter()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">InsertAll()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
      <td height="22" width="8%"><font size="2">O(m+n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">FindAll()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Remove()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)$</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveFirst()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveLast()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">View()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Slide() (amount: d)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(d)</font></td>
      <td height="22" width="8%"><font size="2">O(d)</font></td>
      <td height="22" width="8%"><font size="2">O(d)</font></td>
      <td height="22" width="8%"><font size="2">O(d)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Reverse()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">IsSorted()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Sort()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
      <td height="22" width="8%"><font size="2">O(n log n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Shuffle()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">IPriorityQueue&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">FindMin()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">DeleteMin()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">FindMax()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="30" width="9%"><font size="2">DeleteMax()</font></td>
      <td height="30" width="8%"><font size="2">-</font></td>
      <td height="30" width="8%"><font size="2">-</font></td>
      <td height="30" width="8%"><font size="2">-</font></td>
      <td height="30" width="8%"><font size="2">-</font></td>
      <td height="30" width="8%"><font size="2">-</font></td>
      <td height="30" width="8%"><font size="2">-</font></td>
      <td height="30" width="8%"><font size="2">O(log n)</font></td>
      <td height="30" width="8%"><font size="2">O(log n)</font></td>
      <td height="30" width="9%"><font size="2">O(log n)</font></td>
      <td height="30" width="9%"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td height="30" width="9%"> <font size="2">Comparer</font></td>
      <td height="30" width="8%"> <font size="2">-</font></td>
      <td height="30" width="8%"> <font size="2">-</font></td>
      <td height="30" width="8%"> <font size="2">-</font></td>
      <td height="30" width="8%"> <font size="2">-</font></td>
      <td height="30" width="8%"> <font size="2">-</font></td>
      <td height="30" width="8%"> <font size="2">-</font></td>
      <td height="30" width="8%"> <font size="2">O(1)</font></td>
      <td height="30" width="8%"> <font size="2">O(1)</font></td>
      <td height="30" width="9%"> <font size="2">O(1)</font></td>
      <td height="30" width="9%"> <font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">ISorted&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Predecessor</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Successor</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">WeakPredecessor</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">WeakSuccessor</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Cut</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RangeFrom</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RangeFromTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RangeTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RangeAll</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">AddSorted</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">?</font></td>
      <td height="22" width="8%"><font size="2">?</font></td>
      <td height="22" width="9%"><font size="2">?</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveRangeFrom</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveRangeFromTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RemoveRangeTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
      <td height="22" width="8%"><font size="2">O(nlog n)*</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">IIndexedSorted&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Map</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">CountFrom</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">CountFromTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">CountTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RangeFrom</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RangeFromTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">RangeTo</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="8%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">O(log n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">FindAll</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="8%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">O(n)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
    <tr>
      <td height="22" width="14%"><i><font color="#808080" size="2">IPersistentSorted&lt;T&gt;</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HB</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">AL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">LL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HAL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">HLL</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTS</font></i></td>
      <td height="22" width="8%"><i><font color="#808080" size="2">RBTB</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">SA</font></i></td>
      <td height="22" width="9%"><i><font color="#808080" size="2">IH</font></i></td>
    </tr>
    <tr>
      <td height="22" width="9%"><font size="2">Snapshot()</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">-</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="8%"><font size="2">O(1)</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
      <td height="22" width="9%"><font size="2">-</font></td>
    </tr>
  </tbody>
</table>
<h1><a class="mozTocH1" name="mozTocId712409"></a><a
 name="PerformanceDict">Performance</a> details for dictionary classes</h1>
<table border="1" width="467">
  <tbody>
    <tr>
      <th width="302">Member</th>
      <th width="79">HashDictionary&lt;K,V&gt;</th>
      <th width="64">TreeDictionary&lt;K,V&gt;</th>
    </tr>
    <tr>
      <td width="302"><i><font color="#808080" size="2">IEnumerable&lt;KeyValuePair&lt;K,V&gt;&gt;</font></i></td>
      <td width="79"><font color="#808080">&nbsp;</font></td>
      <td width="64">&nbsp;</td>
    </tr>
    <tr>
      <td width="302"><font size="2">GetEnumerator()</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td width="64"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td width="302"><i><font color="#808080" size="2">IDictionary&lt;K,V&gt;</font></i></td>
      <td width="79"><font color="#808080">&nbsp;</font></td>
      <td width="64">&nbsp;</td>
    </tr>
    <tr>
      <td width="302"><font size="2">this[key]</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Count</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td width="64"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">IsReadOnly</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td width="64"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">SyncRoot</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td width="64"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Keys</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td width="64"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Values</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td width="64"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Add()</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Remove()</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Clear()</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(1)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Contains()</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Find()</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">Update()</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">FindOrAdd</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><font size="2">UpdateOrAdd</font></td>
      <td width="79"><font size="2">O(1)</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td width="302"><i><font color="#808080" size="2">ISortedDictionary&lt;K,V&gt;</font></i></td>
      <td width="79"><font color="#808080">&nbsp;</font></td>
      <td width="64">&nbsp;</td>
    </tr>
    <tr>
      <td height="22" width="302"><font size="2">Predecessor</font></td>
      <td width="79"><font size="2">-</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td height="22" width="302"><font size="2">Successor</font></td>
      <td width="79"><font size="2">-</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td height="22" width="302"><font size="2">WeakPredecessor</font></td>
      <td width="79"><font size="2">-</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
    <tr>
      <td height="22" width="302"><font size="2">WeakSuccessor</font></td>
      <td width="79"><font size="2">-</font></td>
      <td height="22" width="64"><font size="2">O(log n)</font></td>
    </tr>
  </tbody>
</table>
</body>
</html>
